{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction to Linear Programming with Scipy\n", "\n", "## Try me\n", "[![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/CLP/libraries/Scipy%20Linprog%20tutorial.ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FCLP%2Flibraries%2FScipy%20Linprog%20tutorial.ipynb)\n", "\n", "## Requirements\n", "### Install in your environment\n", "#### Google Colabs installation\n", "\n", "> ☝ Scipy is already installed in Google Colabs, no installation required!\n", "\n", "#### Scipy Installation\n", "The simplest way to install SciPy in your environment is using [pip](https://pypi.org/project/pip/). If you have installed\n", "Python and pip in your environment, just open a terminal and try:\n", "\n", "```\n", "pip install scipy\n", "```\n", "#### Conda Installation\n", "If you use Conda, open a Conda Terminal and try: \n", "\n", "```\n", "conda install scipy\n", "```\n", "\n" ] }, { "cell_type": "markdown", "source": [ "#### Binder installation\n", "Run the following code cell to try this notebook in Binder:\n" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "!pip install pandas\n", "!pip install numpy\n", "!pip install scipy\n" ], "metadata": { "collapsed": false, "pycharm": { "is_executing": true } } }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Linear Optimisation with Scipy\n", "In this tutorial, we will learn to model and solve Linear Programming Problems using the Python open source scientific library [Scipy](https://scipy.org/). SciPy is an awesome library extensively used for scientific and technical computing. It is built on top of NumPy and provides a wide range of functionality including optimization, signal processing, interpolation, and more. It also contains modules for linear algebra, optimization, and integration. SciPy is widely used in the scientific and engineering communities and is a powerful tool for data analysis and visualization.\n", "\n", "In this tutorial, we will learn how to use SciPy to model and solve CLP problems. Just as with the previous tutorial, to guide this example, we will use a simple CLP formulated in class:\n", "\n", "maximise $z = 300x + 250y$\n", "\n", "Subject to:\n", "\n", "$$2x + y \\leq 40$$\n", "\n", "\n", "$$x + 3y \\leq 45$$\n", "\n", "\n", "$$x \\leq 12$$\n" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "# Let's start importing the linprog function of the optimize package of SciPy\n", "from scipy.optimize import linprog\n", "# We are going to use panda to display the results as tables using Panda\n", "import pandas as pd\n", "#And we will use numpy to perform array operations\n", "import numpy as np\n", "#We will use display and Markdown to format the output of code cells as Markdown\n", "from IPython.display import display, Markdown" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problem function linprog\n", "#### Transforming the problem model\n", "The function ```linprog``` of the Scipy package can be used to solve continuous linear programming problems expressed in the form:\n", "\n", "$$\\min z = c^T*x$$\n", "\n", "s.t.\n", "\n", "$$A_{ub}*x \\leq b_{ub}$$\n", "$$A_{uc}*x = b_{uc}$$\n", "$$l \\leq x \\leq u$$\n", "\n", "Where $x$ is a (column) vector with the decision variables, $c$ is a (column) vector with the objective function coefficients, $z$ is the objective variable (scalar), $A_{ub}$ is a matrix with the LHS coefficients of the constraints of type *less or equal*, and $b_ub$ is a vector that contains the corresponding RHS coefficients of the same constraints, and finally, $A_{uc}$ is a matrix with the LHS coeffients of type *equal*, and $b_ub$ is a vector that contains the corresponding RHS coefficients.\n", "\n", "This means that we need to convert our problem to comply with the format expected by ```linprog```. In our example, we can convert the objective function as:\n", "\n", "\n", "$\\min z* = - z = -300*x - 250y = [-300, -250]^T*[x, y]$\n", "\n", "That is, since our objective function is of type *maximize*, we use the equivalent minimization problem and the solution will be the negative of our original objective variable. As for the constraint, we need to express all the constraint (except the bounds) as of type *less_or_equal*. In our case, we do not need to apply any transformation, and our matrix $A_{ub}$ becomes:\n", "\n", "\n", "$A_{ub} = \\begin{bmatrix}\n", "2 & 1\\\\\n", "1 & 3\\\\\n", "1 & 0\n", "\\end{bmatrix}$\n", "\n", "Note that the each rows correspond to a constraint, therefore, the vector $b_{ub}$ is:\n", "\n", "$b_{ub} = [40, 45, 12]^T$\n", "\n", "Now, $l$ is going to contain the minimum values of the decision variables, or **lower bound**. Since both variables need to be non-negative:\n", "\n", "$l = [0, 0]$\n", "\n", "and finally, $u$ is going to contain the maximum values or **upper bound**, since x cannot be higher than 12, the upper bounds are:\n", "\n", "\n", "$u = [12, \\infty]$\n", "\n", "Note that the upper bound for x is already expressed in the third constraint. We could remove this constraint and just use the upper bound, but this make it more difficult to obtain the shadow prices from the solution, so for now, we will use this formulation.\n", "\n", "#### linprog function\n", "The documentation of linprog can be found [here](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html#scipy.optimize.linprog), but in short, it takes the following arguments:\n", "\n", "**linprog** ***(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='highs')***\n", "\n", "- **c**: 1-D array containing the coefficients of the linear objective function to be minimized.\n", "\n", "- **A_ub**: 2-D array (optional). The inequality constraint matrix. Each row of A_ub specifies the coefficients of a linear inequality constraint on x.\n", "\n", "- **b_ub**: 1-D array (optional). The inequality constraint vector. Each element represents an upper bound on the corresponding value of A_ub @ x.\n", "\n", "- **A_eq**: 2-D array (optional). The equality constraint matrix. Each row of A_eq specifies the coefficients of a linear equality constraint on x.\n", "\n", "- **b_eq**: 1-D array (optional). The equality constraint vector. Each element of A_eq @ x must equal the corresponding element of b_eq.\n", "\n", "- **bounds**: sequence: (optional). A sequence of (min, max) pairs for each element in x, defining the minimum and maximum values of that decision variable. Use None to indicate that there is no bound. By default, bounds are (0, None) (all decision variables are non-negative). If a single tuple (min, max) is provided, then min and max will serve as bounds for all decision variables.\n", "\n", "- **method**: string (optional). This is the method-specific documentation for ‘highs’, which chooses automatically between ‘highs-ds’ and ‘highs-ipm’. ‘interior-point’ (default), ‘revised simplex’, and ‘simplex’ (legacy) are also available." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "result of the objective function is: 6350.0\n", "result of the decision variables is: [12. 11.]\n", "Optimization terminated successfully. (HiGHS Status 7: Optimal)\n" ] } ], "source": [ "# objective coefficient vector\n", "c = np.array([-300, -250])\n", "# Inequality constraints LHS matrix\n", "A = np.array([[2, 1], [1, 3], [1, 0]])\n", "# Inequality constraints RHS\n", "b = np.array([40, 45, 12])\n", "\n", "#Bounds for x\n", "x_bounds = (0, None) # Here we may as well use 12 as upper bound, but then, we need to read the marginal of the upper bound to learn the shadow price!\n", "# Bounds for y\n", "y_bounds = (0, None)\n", "\n", "res = linprog(c, A_ub=A, b_ub=b, bounds=[x_bounds, y_bounds])\n", "print(f\"result of the objective function is: {-res.fun}\")\n", "print(f\"result of the decision variables is: {res.x}\")\n", "\n", "print(res.message)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, let us display the solution in a nice table using Pandas. We are going to first display the solution value using markdown and then we will use Pandas to create a table with the results." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": " solution coefficients reduced costs\nx 12.0 300 0.0\ny 11.0 250 0.0", "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
solutioncoefficientsreduced costs
x12.03000.0
y11.02500.0
\n
" }, "metadata": {}, "output_type": "display_data" } ], "source": [ "var_df = pd.DataFrame(index=['x', 'y'])\n", "var_df['solution'] = res.x\n", "var_df['coefficients'] = -c\n", "var_df['reduced costs'] = res.lower.marginals\n", "\n", "display(var_df)" ] }, { "cell_type": "markdown", "source": [ "And now another table with the constraints:" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": 13, "outputs": [ { "data": { "text/plain": " RHS slacks shadow_prices\nMan hours 40 5.0 0.000000\nMachine time 45 0.0 83.333333\nMarketing 12 0.0 216.666667", "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
RHSslacksshadow_prices
Man hours405.00.000000
Machine time450.083.333333
Marketing120.0216.666667
\n
" }, "metadata": {}, "output_type": "display_data" } ], "source": [ "con_df = pd.DataFrame(index=['Man hours', 'Machine time', 'Marketing'])\n", "rhs = b\n", "con_df['RHS'] = rhs\n", "con_df['slacks'] = res.slack\n", "con_df['shadow_prices'] = -res.ineqlin.marginals\n", "display(con_df)" ], "metadata": { "collapsed": false } }, { "cell_type": "markdown", "source": [ "### Solved exercises\n", "The following notebooks include exercises solved with Scipy´s Linprog:\n", "\n", "- [Making Chappie Solved with LinProc](../solved/Making%20Chappie%20(Solved%20linprog).ipynb)" ], "metadata": { "collapsed": false } } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 1 }